package 路径问题;

/**
 * @Date 2024/6/12 12:42
 * @description: 不同路径2
 * .            https://leetcode.cn/problems/unique-paths-ii/description/
 * @Author LittleNight
 */
public class likou63 {

    // 动态规划
    // 是不同路径1 的升级版: https://leetcode.cn/problems/unique-paths/
    public int uniquePathsWithObstacles(int[][] ob) {
        // 1.创建 dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        // 动态规划 这里的是二维, 所以时空都是O(M*N)
        int m = ob.length, n = ob[0].length;
        int[][] dp = new int[m + 1][n + 1];
        // dp[1][1] = 1;
        dp[0][1] = 1;
        // 做好映射关系, 原数组的(0,0) 对应dp表中的(1,1)
        // 这里填的是 dp 表, 所以建议从(1,1) 开始, 也就是dp表多加了一行一列
        // 如果是障碍的话, 就直接忽略, 默认就是 0, 也就是表示到不了
        for(int i = 1; i <= m; i++) { // 从上往下每一行
            for(int j = 1; j <= n; j++) { // 从左往右每一列
                if(ob[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}
